package com.zxy.javaarithmetic.chapter_1_StackQueue;

import java.util.Stack;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_1_StackQueue
 *  @文件名:   P_9_MaxSubMatrix
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/3 17:16
 *  @描述：    给定一个矩阵map,值全为0和1，求其中全为1的矩形区域中，最大的值全为1的矩形。
 */
public class P_9_MaxSubMatrix {

	public static void main(String[] args) {
		int[][] map = new int[][]{{1, 0, 1, 1}, {1, 1, 1, 1}, {1, 1, 1, 0}};
		System.out.println("最大矩阵=" + getMaxSubRect(map));
	}

	private static int getMaxSubRect(int[][] map) {
		if (map == null || map.length == 0) {
			return 0;
		}
		int maxRect = 0;
		int[] heights = new int[map[0].length];
		for (int[] aMap : map) {
			for (int j = 0; j < aMap.length; j++) {
				heights[j] = aMap[j] == 0 ? 0 : heights[j] + 1;
			}
			maxRect = Math.max(maxRectFromBottom(heights), maxRect);
			System.out.println("getMaxSubRect=" + maxRect);
		}

		return maxRect;
	}

	/**
	 * 计算以数组为底能得到值为1的最大矩阵
	 * @param heights
	 * @return
	 */
	private static int maxRectFromBottom(int[] heights) {
		if (heights == null || heights.length == 0) {
			return 0;
		}
		int maxRect = 0;
		Stack<Integer> stack = new Stack<>();
		for (int i = 0; i < heights.length; i++) {
			while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
				int popIndex = stack.pop();
				int k = stack.isEmpty() ? -1 : stack.peek();
				int temp = (i - k - 1) * heights[popIndex];
				System.out.println("maxRectFromBottom1=" + temp);
				maxRect = Math.max(temp, maxRect);
			}
			stack.push(i);
		}
		while (!stack.isEmpty()) {
			int popIndex = stack.pop();
			int k = stack.isEmpty() ? -1 : stack.peek();
			int temp = (heights.length - k - 1) * heights[popIndex];
			System.out.println("maxRectFromBottom2=" + temp);
			maxRect = Math.max((heights.length - k - 1) * heights[popIndex], maxRect);
		}

		return maxRect;
	}

}
